Machine vision systems (or other systems processing 2-dimensional data) often need to resample images to adjust scale, rotation, or other distortions in the original data prior to further processing. This operation is referred to herein as warping. For each point in the output image (rendered result array), several points in the source image are read and a computation performed to determine the value of the result. A well known computationally efficient technique uses bilinear interpolation for this purpose. This algorithm reads four neighboring samples surrounding the sub-sample location in the source image to be rendered (2.times.2 aperture). The hardware described is easily extended to higher-order interpolation kernel techniques which nonetheless fetch a fixed number of surrounding samples.
The location to be rendered may be determined by a number of well-known techniques. One technique suitable for efficient hardware implementation iteratively computes horizontal and vertical difference equations which cause the sampling point to move through the source image at successive sub-sample points. In the current embodiment, these difference equations compute a linear path. This is commonly known as a linear DDA (Digital Differential Analyzer). Various other techniques such as higher order DDAs or a data structure containing pre-computed sub-sample points to be rendered could also benefit from the techniques to be described.
Complex warping (e.g. mapping an annular ring to a rectangular image) using linear DDA hardware typically requires a large number of individual linear segments to be processed. Even a simple rotation requires a new DDA operation to be executed for each row of the output image. The need for the DDA hardware to be reinitialized frequently degrades the efficiency of operation.
A second problem occurs in the rendering process due to the nature of burst-mode memories (e.g. SDRAM, SGRAM). This is because all four neighboring pixels which must be fetched on each step do not generally lie on the same memory row. This can degrade performance as memory addressing repeatedly crosses (thrashes) memory row boundaries during the fetch process.